import java.util.Random;
import java.util.Arrays;

public class Dome {
    private static final int SIZE = 9;
    private static final int SUBGRID_SIZE = 3;

    public static void main(String[] args) {
        int[][] sudoku = generateSudoku();
        // 打印数独矩阵，这里省略打印方法的具体实现
        System.out.println(Arrays.toString(sudoku));
//        printSudoku(sudoku);
    }

    private static int[][] generateSudoku() {
        int[][] board = new int[SIZE][SIZE];
        Random rand = new Random();

        // 填充基础数字（这里简化处理，实际应用可能需要更复杂的策略）
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (rand.nextInt(4) == 0) { // 大约每4个位置填充一个数字，仅作示例
                    board[i][j] = rand.nextInt(SIZE) + 1;
                }
            }
        }

        // 递归回溯填充剩余空位
        if (!solveSudoku(board)) {
            System.out.println("Failed to generate a valid Sudoku puzzle.");
            return null;
        }

        return board;
    }

    private static boolean solveSudoku(int[][] board) {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == 0) {
                    for (int num = 1; num <= SIZE; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;

                            if (solveSudoku(board)) {
                                return true;
                            } else {
                                board[row][col] = 0; // 回溯
                            }
                        }
                    }
                    return false; // 没有合适的数字可以放置，需要回溯
                }
            }
        }
        return true; // 所有位置都已成功填充
    }

    private static boolean isValid(int[][] board, int row, int col, int num) {
        // 检查行
        for (int i = 0; i < SIZE; i++) {
            if (board[row][i] == num) {
                return false;
            }
        }
        // 检查列
        for (int i = 0; i < SIZE; i++) {
            if (board[i][col] == num) {
                return false;
            }
        }
        // 检查小宫格
        int startRow = 3 * (row / SUBGRID_SIZE);
        int startCol = 3 * (col / SUBGRID_SIZE);
        for (int i = 0; i < SUBGRID_SIZE; i++) {
            for (int j = 0; j < SUBGRID_SIZE; j++) {
                if (board[startRow + i][startCol + j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
}
